#include "tabu.h"
#include <omp.h>
#include <list>
#include <random>
#include <ctime>
#include "utils.h"

using namespace std;

Tabu::Tabu(int nTabuSize,int nNeighbor):m_nNeighbor (nNeighbor)
{
    m_pTabu = new TabuList;
    m_nTabuSize = nTabuSize;
    m_nParallelNum = omp_get_num_procs();
}

Tabu::~Tabu()
{
    delete m_pTabu;
}

void Tabu::run(MatrixX<int> &mat,MatrixX<int> &firstSolve,int maxStep)
{
    int tmpBestIndex = 0;
    int nbMoves = 0;
    int nBestVal = 0;
    unsigned char tmpVal = 0;
    bool stop = false;
    bool bHasBetter = false;
    BestNeighborType bestNeighbor;
    MatrixX<int> tmpBestSol = firstSolve;
    MatrixX<int> tmpCrossSol = firstSolve;

    default_random_engine e(time(0));
    uniform_int_distribution<unsigned> u(0, 2999);
    m_matVec.resize(m_nParallelNum);

    omp_set_num_threads(m_nParallelNum);
    while(nbMoves < maxStep && !stop)
    {
        {
            #pragma omp parallel
            {
                auto &iter = m_matVec[omp_get_thread_num()];
                iter.solve = tmpBestSol;
                getBestNeighbor(mat, iter,u(e));
            }

#if 0 //杂交最优解
            tmpBestIndex = 0;
            for(auto i = 0; i < m_matVec.size(); i++)
            {
                auto &iter = m_matVec[i];
                bHasBetter = isBetterNeighb(mat, tmpBestSol, std::get<0>(iter),nBestVal);
                if(bHasBetter)
                {
                    tmpBestIndex = i;
                    tmpBestSol = std::get<0>(iter);
                    bestNeighbor = iter;
                }
            }

            //选择最好的和次好的进行杂交
            tmpCrossSol = tmpBestSol;
            for(auto i = 0; i < m_matVec.size(); i++)
            {
                if(i == tmpBestIndex)
                {
                    continue;
                }
                auto &iter = m_matVec[i];
                tmpVal = tmpCrossSol.data()[std::get<1>(iter)];
                tmpCrossSol.data()[std::get<1>(iter)] = tmpCrossSol.data()[std::get<2>(iter)];
                tmpCrossSol.data()[std::get<2>(iter)] = tmpVal;
                bHasBetter = isBetterNeighb(mat, tmpBestSol, tmpCrossSol,nBestVal);
                if(bHasBetter)
                {
                    tmpBestSol = tmpCrossSol;
                }
                else
                {
                    tmpCrossSol.data()[std::get<2>(iter)] = tmpCrossSol.data()[std::get<1>(iter)];
                    tmpCrossSol.data()[std::get<1>(iter)] = tmpVal;
                }
            }
#elif 1 //不杂交最优解
            for(auto &iter : m_matVec)
            {
                bHasBetter = isBetterNeighb(mat, tmpBestSol, iter.solve,nBestVal);
                if(bHasBetter)
                {
                    tmpBestSol = iter.solve;
                    bestNeighbor = iter;
                }
            }
#endif

            addTabu(bestNeighbor.posX,
                    bestNeighbor.posY, nBestVal, bHasBetter);

            nbMoves++;
        }

        if(nbMoves % 20 == 0)
        {
            printf("calc step: %d best is: %d\n",nbMoves, calcCost(mat,tmpBestSol));
        }
    }

    firstSolve = tmpBestSol;
}

void Tabu::addTabu(int posX,int posY,int nVal,bool bIsBest)
{
    if(!bIsBest)
    {
        //禁忌判断
        for(auto & iter:(*m_pTabu))
        {
            if(iter.posX == posX && posY == iter.posY)
            {
                return;
            }
            if(iter.posX == posY && posY == iter.posX)
            {
                return;
            }
        }
    }

    if(m_pTabu->size() == m_nTabuSize && bIsBest)
    {
        m_pTabu->erase(m_pTabu->begin());
        m_pTabu->emplace_back(posX,posY,nVal);
    }
    else if(m_pTabu->size() < m_nTabuSize)
    {
        m_pTabu->emplace_back(posX,posY,nVal);
    }
}

void Tabu::getBestNeighbor(MatrixX<int> &mat, BestNeighborType &bestNeighbor, int nStartIndex)
{
    bool firstChange = true;
    MatrixX<int> tpMat = bestNeighbor.solve;
    int numIndex = 0;
    int posX = nStartIndex, posY = 0,xVal,yVal,tpVal;

    for(int i = 1; i < m_nNeighbor; )
    {
        //交换位置确定
        {
            ++numIndex;
            posY = (nStartIndex + numIndex) % 3000;
            if(tpMat.data()[posX] == tpMat.data()[posY])
            {
                continue;
            }
        }

        xVal = tpMat.data()[posX];
        yVal = tpMat.data()[posY];
        tpMat.data()[posX] = yVal;
        tpMat.data()[posY] = xVal;

        if(isBetterNeighb(mat, bestNeighbor.solve, tpMat))
        {
            if(!firstChange)
            {
                tpVal = bestNeighbor.solve.data()[bestNeighbor.posX];
                bestNeighbor.solve.data()[bestNeighbor.posX] = bestNeighbor.solve.data()[bestNeighbor.posY];
                bestNeighbor.solve.data()[bestNeighbor.posY] = tpVal;
            }
            firstChange = false;

            bestNeighbor.solve.data()[posX] = yVal;
            bestNeighbor.solve.data()[posY] = xVal;
            bestNeighbor.posX = posX;
            bestNeighbor.posY = posY;
        }
        //交换回来
        tpMat.data()[posY] = yVal;
        tpMat.data()[posX] = xVal;
        i++;
    }
}

inline bool Tabu::isBetterNeighb(MatrixX<int> &mat, MatrixX<int> &solve1, MatrixX<int> &solve2,int &bestVal)
{
    int cost0 = calcCost(mat, solve1);
    int cost1 = calcCost(mat, solve2);
    if(cost0 < cost1)
    {
        bestVal = cost1;
        return true;
    }
    bestVal = cost0;

    return false;
}

inline bool Tabu::isBetterNeighb(MatrixX<int> &mat, MatrixX<int> &solve1, MatrixX<int> &solve2)
{
    int cost0 = calcCost(mat, solve1);
    int cost1 = calcCost(mat, solve2);
    return cost0 < cost1;
}

inline int Tabu::calcCost(MatrixX<int> &mat,MatrixX<int> &solve)
{
    auto ret = solve * mat * solve.transpose();
    return ret.coeff(0,0);
}
